|
The Chandra–Toueg consensus algorithm, published by Tushar Deepak Chandra and Sam Toueg in 1996, is an algorithm for solving consensus in a network of unreliable processes equipped with an ''eventually strong'' failure detector. The failure detector is an abstract version of timeouts; it signals to each process when other processes may have crashed. An eventually strong failure detector is one that never identifies some specific good process as having failed after some initial period of confusion, and at the same time eventually identifies all bad processes as failed. The algorithm itself is similar to the Paxos algorithm, which also relies on failure detectors. Both algorithms assume the number of faulty processes is less than n/2, where n is the total number of processes. == The algorithm == The algorithm proceeds in rounds and uses a rotating coordinator: in each round r, the process whose identity is given by r mod n is chosen as the coordinator. Each process keeps track of its current preferred decision value (initially equal to the input of the process) and the last round where it changed its decision value (the value's timestamp). The actions carried out in each round are: # All processes send (r, preference, timestamp) to the coordinator. # The coordinator waits to receive messages from at least half of the processes (including itself). It then chooses as its preference a value with the most recent timestamp among those sent. # The coordinator sends (r, preference) to all processes. # Each process waits to receive (r, preference) from the coordinator or for its failure detector to identify the coordinator as crashed. In the first case, it sets its own preference to the coordinator's preference and responds with ack(r). In the second case, it sends nack(r) to the coordinator. # The coordinator waits to receive ack(r) or nack(r) from a majority of processes. If it receives ack(r) from a majority, it sends decide(preference) to all processes. # Any process that receives decide(preference) for the first time sends decide(preference) to all processes, then decides preference and terminates. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chandra–Toueg consensus algorithm」の詳細全文を読む スポンサード リンク
|